package leetcode.code;

/**
 * 给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。
 *
 * update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
 *
 * 示例:
 *
 * Given nums = [1, 3, 5]
 *
 * sumRange(0, 2) -> 9
 * update(1, 2)
 * sumRange(0, 2) -> 8
 * 说明:
 *
 * 数组仅可以在 update 函数下进行修改。
 * 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-mutable
 */
public class 区域和检索_数组可修改_线段树 {


    class NumArray {

        private int[] numArray;

        public NumArray(int[] nums) {
            this.numArray = nums;
        }

        public void update(int i, int val) {
            this.numArray[i] = val;
        }

        public int sumRange(int i, int j) {
            int tmp = 0;
            for (int x = i; x <= j; x++){
                tmp += numArray[x];
            }
            return tmp;
        }
    }

    /**
     * sqrt 分解
     * 其思想是将数组分割成块，块的长度为 \sqrt n
     * n
     * ​
     *  。然后我们计算每个块的和，并将其存储在辅助存储器 b 中。要查询 RSQ(i, j)，我们将添加位于内部的所有块和部分在范围 [i\ldots j][i…j] 重叠的块的总和。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/range-sum-query-mutable/solution/qu-yu-he-jian-suo-shu-zu-ke-xiu-gai-by-leetcode/
     * 来源：力扣（LeetCode）
     */
    class Sqrt{
        private int[] b;
        private int len;
        private int[] nums;

        public Sqrt(int[] nums) {
            this.nums = nums;
            double l = Math.sqrt(nums.length);
            len = (int) Math.ceil(nums.length/l);
            b = new int [len];
            for (int i = 0; i < nums.length; i++)
                b[i / len] += nums[i];
        }

        public int sumRange(int i, int j) {
            int sum = 0;
            int startBlock = i / len;
            int endBlock = j / len;
            if (startBlock == endBlock) {
                for (int k = i; k <= j; k++)
                    sum += nums[k];
            } else {
                for (int k = i; k <= (startBlock + 1) * len - 1; k++)
                    sum += nums[k];
                for (int k = startBlock + 1; k <= endBlock - 1; k++)
                    sum += b[k];
                for (int k = endBlock * len; k <= j; k++)
                    sum += nums[k];
            }
            return sum;
        }

        public void update(int i, int val) {
            int b_l = i / len;
            b[b_l] = b[b_l] - nums[i] + val;
            nums[i] = val;
        }
    }
    /**
     * 线段树
     * 算法：
     * 线段树是一种非常灵活的数据结构，它可以用于解决多种范围查询问题，比如在对数时间内从数组中找到最小值、最大值、总和、最大公约数、最小公倍数等。
     *
     *
     *
     * 数组 A[0,1,\ldots,n-1]A[0,1,…,n−1] 的线段树是一个二叉树，其中每个节点都包含数组的一个子范围 [i\ldots j][i…j] 上的聚合信息（最小值、最大值、总和等），其左、右子节点分别包含范围 [i \ldots \frac{i+j}{2}][i…
     * 2
     * i+j
     * ​
     *  ] 和 [\frac{i + j}{2} + 1, j][
     * 2
     * i+j
     * ​
     *  +1,j] 上的信息。
     *
     * 线段树既可以用数组也可以用树来实现。对于数组实现，如果索引 ii处的元素不是一个叶节点，那么其左子节点和右子节点分别存储在索引为 2i 和 2i+1的元素处。
     *
     * 在上图所给出的示例中，每个叶节点都包含初始的数组元素 {2,4,5,7,8,9}。内部节点包含范围内相应元素的总和 - (11) 是从索引 0 到索引 2 的元素之和。而根节点 (35) 是它的两个子节点 (6) 和 (29) 的和,也是整个数组的和。
     *
     * 线段树可以分为以下三个步骤：
     *
     * 从给定数组构建线段树的预处理步骤。
     * 修改元素时更新线段树。
     * 使用线段树进行区域和检索。
     * 构建线段树 :
     * 我们将使用一种非常有效的自下而上的方法来构建线段树。从上面我们已经知道，如果某个节点 pp 包含范围 [i\ldots j][i…j] 的和，那么其左、右子节点分别包含范围 [i \ldots \frac{i + j}{2}][i…
     * 2
     * i+j
     * ​
     *  ] 和 [\frac{i + j}{2} + 1, j][
     * 2
     * i+j
     * ​
     *  +1,j] 上的和。
     *
     * 因此，为了找到节点 pp 的和，我们需要提前计算其左、右子节点的和。
     *
     * 我们从叶节点开始，用输入数组的元素 a[0,1,\ldots,n-1]a[0,1,…,n−1] 初始化它们。然后我们逐步向上移动到更高一层来计算父节点的和，直到最后到达线段树的根节点。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/range-sum-query-mutable/solution/qu-yu-he-jian-suo-shu-zu-ke-xiu-gai-by-leetcode/
     * 来源：力扣（LeetCode）
     */
    class Tree {
        int[] tree;
        int n;
        public Tree(int[] nums) {
            if (nums.length > 0) {
                n = nums.length;
                tree = new int[n * 2];
                buildTree(nums);
            }
        }

        /**
         * 我们从叶节点开始，用输入数组的元素 a[0,1,...,n-1]初始化它们。
         * 然后我们逐步向上移动到更高一层来计算父节点的和，直到最后到达线段树的根节点。
         * @param nums data
         */
        private void buildTree(int[] nums) {
            for (int i = n, j = 0;  i < 2 * n; i++,  j++)
                tree[i] = nums[j];
            for (int i = n - 1; i > 0; --i)
                tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }

        void update(int pos, int val) {
            pos += n; // 定位到叶子节点
            tree[pos] = val;
            while (pos > 0) {
                int left = pos;
                int right = pos;
                if (pos % 2 == 0) {
                    right = pos + 1;
                } else {
                    left = pos - 1;
                }
                // parent is updated after child is updated
                tree[pos / 2] = tree[left] + tree[right];
                pos /= 2;
            }
        }

        public int sumRange(int l, int r) {
            // get leaf with value 'l'
            l += n;
            // get leaf with value 'r'
            r += n;
            int sum = 0;
            while (l <= r) {
                if ((l % 2) == 1) { // 要么是l与r相遇 要么是孤儿叶子节点
                    sum += tree[l];
                    l++;
                }
                if ((r % 2) == 0) {
                    sum += tree[r];
                    r--;
                }
                l /= 2;
                r /= 2;
            }
            return sum;
        }

    }

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
}
